/**
 * 
 */
package string.passed;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * @author xyyi
 * Solution liknk
 *http://discuss.leetcode.com/questions/210/substring-with-concatenation-of-all-words
 */
public class SubstringwithConcatenationofAllWords {

	/**
	You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.

	For example, given:
	S: "barfoothefoobarman"
	L: ["foo", "bar"]

	You should return the indices: [0,9].
	(order does not matter).
	 */

	// TODO this solution didi not work
	public ArrayList<Integer> findSubstring(String S, String[] L) {
		// Start typing your Java solution below
		// DO NOT write main() function
		HashMap<String, Integer> hasFound = new HashMap<String, Integer>();
		HashMap<String, Integer> needToFind = new HashMap<String, Integer>();
		int counter = 0;
		int wordLen = L[0].length();
		ArrayList<Integer> results = new ArrayList<Integer>();

		for (String word : L) {
			if (!needToFind.containsKey(word)) {
				needToFind.put(word, 1);
			} else {
				needToFind.put(word, needToFind.get(word) + 1);
			}
			if (!hasFound.containsKey(word)) {
				hasFound.put(word, 0);
			}
		}

		int left = 0, right = 0;
		while (right <= S.length() - wordLen) {
			String word = S.substring(right, right + wordLen);
			if (needToFind.containsKey(word)
					&& hasFound.get(word) < needToFind.get(word)) {
				right += wordLen;
				counter++;
				hasFound.put(word, hasFound.get(word) + 1);
			} else if (needToFind.containsKey(word)
					&& hasFound.get(word) >= needToFind.get(word)) {
				String leftWord = S.substring(left, left + wordLen);
				while (left <= S.length() - wordLen
						&& needToFind.containsKey(leftWord)) {
					if (!word.equals(leftWord)) {
						hasFound.put(leftWord, hasFound.get(leftWord) - 1);
						left = left + wordLen;
						counter--;
						leftWord = S.substring(left, left + wordLen);
					} else {
						break;
					}
				}
				right = right + wordLen;
				left = left + wordLen;
			} else {
				right++;
				left = right;
				counter = 0;
				for (String key : hasFound.keySet()) {
					hasFound.put(key, 0);
				}
				continue;
			}

			if (counter == L.length) {
				while (left <= S.length() - wordLen
						&& !needToFind.containsKey(S.substring(left, left
								+ wordLen))) {
					left++;
				}
				if (right - left == L.length * wordLen) {
					results.add(left);
				}
			}
		}

		return results;
	}

	/**
	 * 
	 */
	public SubstringwithConcatenationofAllWords() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		SubstringwithConcatenationofAllWords scfw = new SubstringwithConcatenationofAllWords();
		//String S = "lingmindraboofooowingdingbarrwingmonkeypoundcake";

		String S = "abaababbaba";
		String[] L = { "ab", "ba", "ab", "ba" };
		List<Integer> index = scfw.findSubstring(S, L);
	}
}
